#include <cstdlib>
#include <deque>
#include <iostream>
#include <queue>
#include <vector>

/**
 * PAT A 1111 Online Map
 */

struct Edge {
    int to;
    int len;
    int time;

    Edge(int to, int len, int time) : to(to), len(len), time(time) {}
};

struct Vertex {
    int index;
    std::vector<Edge> edges;
    int len, time, isect;
    int prev;

    Vertex(int index) : index(index) {}
};

struct Shorter {
    int metric(Vertex *v) const { return v->len; }

    bool operator()(Vertex *u, Vertex *v) const {
        return (u->len > v->len) || (u->len == v->len && u->time > v->time);
    }

    bool update(Vertex *u, Vertex *v, Edge *e) const {
        bool ok = (u->len + e->len < v->len) ||
                  (u->len + e->len == v->len && u->time + e->time < v->time);
        if (ok) {
            v->len = u->len + e->len;
            v->time = u->time + e->time;
            return true;
        } else
            return false;
    }
};

struct Faster {
    int metric(Vertex *v) const { return v->time; }

    bool operator()(Vertex *u, Vertex *v) const {
        return (u->time > v->time) || (u->time == v->time && u->isect > v->isect);
    }

    bool update(Vertex *u, Vertex *v, Edge *e) const {
        bool ok = (u->time + e->time < v->time) ||
                  (u->time + e->time == v->time && u->isect + 1 < v->isect);
        if (ok) {
            v->time = u->time + e->time;
            v->isect = u->isect + 1;
            return true;
        } else
            return false;
    }
};

struct Result {
    int metric;
    std::deque<int> path;

    Result(int metric, const std::deque<int> &path)
        : metric(metric), path(path) {}
};

std::vector<Vertex> vertices;

template <class F>
Result findShortestPath(int src, int dst) {
    // Initialize vertices
    std::priority_queue<Vertex *, std::deque<Vertex *>, F> heap;
    Vertex *srcVert = &vertices[src];
    heap.push(srcVert);
    for (std::vector<Vertex>::iterator iter = vertices.begin();
         iter != vertices.end(); iter++) {
        iter->len = INT32_MAX;
        iter->time = INT32_MAX;
        iter->isect = INT32_MAX;
        iter->prev = -1;
    }
    srcVert->len = 0;
    srcVert->time = 0;
    srcVert->isect = 0;

    // Find shortest path
    while (!heap.empty()) {
        Vertex *vert = heap.top();
        int curIdx = vert->index;
        heap.pop();

        for (std::vector<Edge>::iterator iter = vert->edges.begin();
             iter != vert->edges.end(); iter++) {
            int otherIdx = iter->to;
            Vertex *other = &vertices[otherIdx];
            if (F().update(vert, other, &*iter)) {
                other->prev = curIdx;
                heap.push(other);
            }
        }
    }

    // Collect result
    Vertex *dstVert = &vertices[dst];
    int metric = F().metric(dstVert);
    std::deque<int> path;
    int idx = dst;
    while (idx != -1) {
        path.push_front(idx);
        idx = vertices[idx].prev;
    }
    return Result(metric, path);
}

void printPath(const std::deque<int> &path) {
    printf("%d", path[0]);
    for (int i = 1; i < path.size(); i++) printf(" -> %d", path[i]);
    printf("\n");
}

int main() {
    // Read map
    int nVerts, nEdges;
    scanf("%d %d", &nVerts, &nEdges);
    vertices.reserve(nVerts);
    for (int i = 0; i < nVerts; i++) vertices.push_back(Vertex(i));
    for (int i = 0; i < nEdges; i++) {
        int from, to, oneWay, len, time;
        scanf("%d %d %d %d %d", &from, &to, &oneWay, &len, &time);
        vertices[from].edges.push_back(Edge(to, len, time));
        if (!oneWay) vertices[to].edges.push_back(Edge(from, len, time));
    }

    // Find shortest path under two metrics
    int src, dst;
    scanf("%d %d", &src, &dst);
    Result distRes = findShortestPath<Shorter>(src, dst);
    Result timeRes = findShortestPath<Faster>(src, dst);
    if (distRes.path == timeRes.path) {
        printf("Distance = %d; Time = %d: ", distRes.metric, timeRes.metric);
        printPath(distRes.path);
    } else {
        printf("Distance = %d: ", distRes.metric);
        printPath(distRes.path);
        printf("Time = %d: ", timeRes.metric);
        printPath(timeRes.path);
    }

    return 0;
}